package jzoffer;

/**
 * 使用动态规划
 * dp[i] 代表以nums[i]为结尾的最大连续子数组的数据和
 * 如果 dp[i-1]>0 则 dp[i] = dp[i-1]+ nums[i]
 * 否则 dp[i] = nums[i]
 * @author MaoLin Wang
 * @date 2020/10/19 5:01 下午
 */
public class _42连续子数组的最大和 {
    public int maxSubArray(int[] nums) {
        if (nums==null|| nums.length==0){
            return 0;
        }
        int[]dp=new int[nums.length];
        int res=0;
        dp[0]=nums[0];
        for (int i = 1; i <nums.length ; i++) {
            if (dp[i-1]<=0){
                dp[i]=nums[i];
            }else {
                dp[i]=nums[i]+dp[i-1];
            }
            res=Math.max(res,dp[i]);
        }
        return res;
    }
}
